//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。 
//
// 
//
// 
//
// 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。 
//
// 
//
// 
//
// 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。 
//
// 
//
// 示例: 
//
// 输入: [2,1,5,6,2,3]
//输出: 10 
// Related Topics 栈 数组 
// 👍 1408 👎 0


package service.week01.leetcode.editor.cn;

import java.util.Arrays;
import java.util.Stack;

//Java：柱状图中最大的矩形
public class P84LargestRectangleInHistogram {
    public static void main(String[] args) {
        Solution solution = new P84LargestRectangleInHistogram().new Solution();
        // TO TEST
        solution.largestRectangleArea(new int[]{1,2,3});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 单调栈
         *
         * @param heights
         * @return
         */
        public int largestRectangleArea(int[] heights) {
            int n = heights.length;
            //n+1 是为了清空栈 比如1，2，3
            int[] heightsWithZero = Arrays.copyOf(heights, n + 1);
            //帮助清空栈
            Stack<Rect> stack = new Stack<>();
            int res = 0;
            for (int i : heightsWithZero) {
                int width = 0;
                //不满足单调栈则出栈
                while (!stack.isEmpty() && stack.peek().height >= i) {
                    width = width + stack.peek().width;
                    res = Math.max(res, width * stack.peek().height);
                    stack.pop();
                }
                //新元素入栈
                Rect rect = new Rect();
                rect.height = i;
                rect.width = width + 1;
                stack.push(rect);
            }
            return res;
        }

        private class Rect {
            public int height;
            public int width;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}